Search Results

Documents authored by Durand, Arnaud

Document
DOI: 10.4230/LIPIcs.MFCS.2022.38
Enumeration Classes Defined by Circuits

Authors: Nadia Creignou, Arnaud Durand, and Heribert Vollmer

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in DelayP, for which a formal way of comparison was not possible to this day.
Cite as

Nadia Creignou, Arnaud Durand, and Heribert Vollmer. Enumeration Classes Defined by Circuits. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{creignou_et_al:LIPIcs.MFCS.2022.38,
  author =	{Creignou, Nadia and Durand, Arnaud and Vollmer, Heribert},
  title =	{{Enumeration Classes Defined by Circuits}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.38},
  URN =		{urn:nbn:de:0030-drops-168364},
  doi =		{10.4230/LIPIcs.MFCS.2022.38},
  annote =	{Keywords: Computational complexity, enumeration problem, Boolean circuit}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.23
Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations

Authors: Olivier Bournez and Arnaud Durand

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
This paper studies the expressive and computational power of discrete Ordinary Differential Equations (ODEs). It presents a new framework using discrete ODEs as a central tool for computation and algorithm design. We present the general theory of discrete ODEs for computation theory, we illustrate this with various examples of algorithms, and we provide several implicit characterizations of complexity and computability classes. The proposed framework presents an original point of view on complexity and computation classes. It unifies several constructions that have been proposed for characterizing these classes including classical approaches in implicit complexity using restricted recursion schemes, as well as recent characterizations of computability and complexity by classes of continuous ordinary differential equations. It also helps understanding the relationships between analog computations and classical discrete models of computation theory. At a more technical point of view, this paper points out the fundamental role of linear (discrete) ordinary differential equations and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming many algorithms.
Cite as

Olivier Bournez and Arnaud Durand. Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bournez_et_al:LIPIcs.MFCS.2019.23,
  author =	{Bournez, Olivier and Durand, Arnaud},
  title =	{{Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.23},
  URN =		{urn:nbn:de:0030-drops-109670},
  doi =		{10.4230/LIPIcs.MFCS.2019.23},
  annote =	{Keywords: Implicit complexity, discrete ordinary differential equations, recursion scheme}
}
Document
DOI: 10.4230/LIPIcs.CSL.2016.20
Descriptive Complexity of #AC^0 Functions

Authors: Arnaud Durand, Anselm Haak, Juha Kontinen, and Heribert Vollmer

Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Abstract
We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. We completely determine the inclusion structure and show that #P and #AC^0 appear as classes of this hierarchy. In this way, we unconditionally place #AC^0 properly in a strict hierarchy of arithmetic classes within #P. We compare our classes with a hierarchy within #P defined in a model-theoretic way by Saluja et al. We argue that our approach is better suited to study arithmetic circuit classes such as #AC^0 which can be descriptively characterized as a class in our framework.
Cite as

Arnaud Durand, Anselm Haak, Juha Kontinen, and Heribert Vollmer. Descriptive Complexity of #AC^0 Functions. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{durand_et_al:LIPIcs.CSL.2016.20,
  author =	{Durand, Arnaud and Haak, Anselm and Kontinen, Juha and Vollmer, Heribert},
  title =	{{Descriptive Complexity of #AC^0 Functions}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Talbot, Jean-Marc and Regnier, Laurent},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.20},
  URN =		{urn:nbn:de:0030-drops-65601},
  doi =		{10.4230/LIPIcs.CSL.2016.20},
  annote =	{Keywords: finite model theory, Fagin's theorem, arithmetic circuits, counting classes, Skolem function}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2014.493
Homomorphism Polynomials Complete for VP

Authors: Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, and Nitin Saurabh

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract
The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant of a matrix of polynomially bounded size. Strikingly, this restatement does not mention any notion of computational model. To get a similar restatement for the original and more fundamental question, and also to better understand the class itself, we need a complete polynomial for VP. Ad hoc constructions yielding complete polynomials were known, but not natural examples in the vein of the determinant. We give here several variants of natural complete polynomials for VP, based on the notion of graph homomorphism polynomials.
Cite as

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, and Nitin Saurabh. Homomorphism Polynomials Complete for VP. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 493-504, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{durand_et_al:LIPIcs.FSTTCS.2014.493,
  author =	{Durand, Arnaud and Mahajan, Meena and Malod, Guillaume and de Rugy-Altherre, Nicolas and Saurabh, Nitin},
  title =	{{Homomorphism Polynomials Complete for VP}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{493--504},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.493},
  URN =		{urn:nbn:de:0030-drops-48665},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.493},
  annote =	{Keywords: algebraic complexity, graph homomorphism, polynomials, VP, VNP, completeness}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.CSL.2012
LIPIcs, Volume 16, CSL'12, Complete Volume

Authors: Patrick Cégielski and Arnaud Durand

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

Abstract
LIPIcs, Volume 16, CSL'12, Complete Volume
Cite as

Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{cegielski_et_al:LIPIcs.CSL.2012,
  title =	{{LIPIcs, Volume 16, CSL'12, Complete Volume}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012},
  URN =		{urn:nbn:de:0030-drops-41106},
  doi =		{10.4230/LIPIcs.CSL.2012},
  annote =	{Keywords: Conference Proceedings; Software; Theory of Computation; Graph Theory; Probability and Statistics; Artificial Intelligence}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.365
The arithmetic complexity of tensor contractions

Authors: Florent Capelli, Arnaud Durand, and Stefan Mengel

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We investigate the algebraic complexity of tensor calulus. We consider a generalization of iterated matrix product to tensors and show that the resulting formulas exactly capture VP, the class of polynomial families efficiently computable by arithmetic circuits. This gives a natural and robust characterization of this complexity class that despite its naturalness is not very well understood so far.
Cite as

Florent Capelli, Arnaud Durand, and Stefan Mengel. The arithmetic complexity of tensor contractions. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 365-376, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{capelli_et_al:LIPIcs.STACS.2013.365,
  author =	{Capelli, Florent and Durand, Arnaud and Mengel, Stefan},
  title =	{{The arithmetic complexity of tensor contractions}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{365--376},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.365},
  URN =		{urn:nbn:de:0030-drops-39481},
  doi =		{10.4230/LIPIcs.STACS.2013.365},
  annote =	{Keywords: algebraic complexity, arithmetic circuits, tensor calculus}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.CSL.2012.i
Frontmatter, Table of Contents, Preface, Conference Organization

Authors: Patrick Cégielski and Arnaud Durand

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

Abstract
Frontmatter, Table of Contents, Preface, Conference Organization
Cite as

Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. i-xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{cegielski_et_al:LIPIcs.CSL.2012.i,
  author =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  title =	{{Frontmatter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{i--xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.i},
  URN =		{urn:nbn:de:0030-drops-36559},
  doi =		{10.4230/LIPIcs.CSL.2012.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2011.252
Dependence logic with a majority quantifier

Authors: Arnaud Durand, Johannes Ebbing, Juha Kontinen, and Heribert Vollmer

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract
We study the extension of dependence logic D by a majority quantifier M over finite structures. We show that the resulting logic is equi-expressive with the extension of second-order logic by second-order majority quantifiers of all arities. Our results imply that, from the point of view of descriptive complexity theory, D(M) captures the complexity class counting hierarchy.
Cite as

Arnaud Durand, Johannes Ebbing, Juha Kontinen, and Heribert Vollmer. Dependence logic with a majority quantifier. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 252-263, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{durand_et_al:LIPIcs.FSTTCS.2011.252,
  author =	{Durand, Arnaud and Ebbing, Johannes and Kontinen, Juha and Vollmer, Heribert},
  title =	{{Dependence logic with a majority quantifier}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{252--263},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.252},
  URN =		{urn:nbn:de:0030-drops-33467},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.252},
  annote =	{Keywords: dependence logic, counting hierarchy, majority quantifier, second order logic, descriptive complexity, finite model theory}
}
Document
DOI: 10.4230/LIPIcs.CSL.2011.189
Enumeration Complexity of Logical Query Problems with Second-order Variables

Authors: Arnaud Durand and Yann Strozecki

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract
We consider query problems defined by first order formulas of the form F(x,T) with free first order and second order variables and study the data complexity of enumerating results of such queries. By considering the number of alternations in the quantifier prefixes of formulas, we show that such query problems either admit a constant delay or a polynomial delay enumeration algorithm or are hard to enumerate. We also exhibit syntactically defined fragments inside the hard cases that still admit good enumeration algorithms and discuss the case of some restricted classes of database structures as inputs.
Cite as

Arnaud Durand and Yann Strozecki. Enumeration Complexity of Logical Query Problems with Second-order Variables. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 189-202, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{durand_et_al:LIPIcs.CSL.2011.189,
  author =	{Durand, Arnaud and Strozecki, Yann},
  title =	{{Enumeration Complexity of Logical Query Problems with Second-order Variables}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{189--202},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.189},
  URN =		{urn:nbn:de:0030-drops-32313},
  doi =		{10.4230/LIPIcs.CSL.2011.189},
  annote =	{Keywords: descriptive complexity, enumeration, query problem}
}
Document
DOI: 10.4230/DagSemProc.06451.4
Counting Results in Weak Formalisms

Authors: Arnaud Durand, Clemens Lautemann, and Malika More

Published in: Dagstuhl Seminar Proceedings, Volume 6451, Circuits, Logic, and Games (2007)

Abstract
The counting ability of weak formalisms is of interest as a measure of their expressive power. The question was investigated in the 1980's in several papers in complexity theory and in weak arithmetic. In each case, the considered formalism (AC$^0$--circuits, first--order logic, $Delta_0$, respectively) was shown to be able to count precisely up to a polylogarithmic number. An essential part of each of the proofs is the construction of a 1--1 mapping from a small subset of ${0,ldots,N-1}$ into a small initial segment. In each case the expressibility of such a mapping depends on some strong argument (group theoretic device or prime number theorem) or intricate construction. We present a coding device based on a collision-free hashing technique, leading to a completely elementary proof for the polylog counting capability of first--order logic (with built--in arithmetic), $AC^0$--circuits, rudimentary arithmetic, the Linear Hierarchy, and monadic--second order logic with addition.
Cite as

Arnaud Durand, Clemens Lautemann, and Malika More. Counting Results in Weak Formalisms. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{durand_et_al:DagSemProc.06451.4,
  author =	{Durand, Arnaud and Lautemann, Clemens and More, Malika},
  title =	{{Counting Results in Weak Formalisms}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6451},
  editor =	{Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.4},
  URN =		{urn:nbn:de:0030-drops-9767},
  doi =		{10.4230/DagSemProc.06451.4},
  annote =	{Keywords: Small complexity classes, logic, polylog counting}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact